#include <bits/stdc++.h>
using namespace std;

/*
2048. 下一个更大的数值平衡数
已解答
中等
相关标签
premium lock icon
相关企业
提示
如果整数  x 满足：对于每个数位 d ，这个数位 恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。

给你一个整数 n ，请你返回 严格大于 n 的 最小数值平衡数 。

 

示例 1：

输入：n = 1
输出：22
解释：
22 是一个数值平衡数，因为：
- 数字 2 出现 2 次 
这也是严格大于 1 的最小数值平衡数。
示例 2：

输入：n = 1000
输出：1333
解释：
1333 是一个数值平衡数，因为：
- 数字 1 出现 1 次。
- 数字 3 出现 3 次。 
这也是严格大于 1000 的最小数值平衡数。
注意，1022 不能作为本输入的答案，因为数字 0 的出现次数超过了 0 。
示例 3：

输入：n = 3000
输出：3133
解释：
3133 是一个数值平衡数，因为：
- 数字 1 出现 1 次。
- 数字 3 出现 3 次。 
这也是严格大于 3000 的最小数值平衡数。
 

提示：

0 <= n <= 106
*/

// 法一
class Solution {
public:
    int nextBeautifulNumber(int n) {
        // 遍历
        for (int x = n + 1; ; x++) {
            if (isBalanced(x)) return x;
        }
    }

    bool isBalanced(int x) {
        vector<int> cnt(10, 0); 
        // 拆分每一位
        while (x > 0) {
            int d = x % 10;
            cnt[d]++;
            x /= 10;
        }
        // check 每个出现过的数字d：出现次数是否等于d
        for (int d = 0; d < 10; d++) {
            if (cnt[d] == 0) continue; // 未出现的数字跳过
            if (cnt[d] != d) return false; // 出现次数不等于自身，不是平衡数
        }
        return true;
    } 
};

// 法二
class Solution {
public:
    int nextBeautifulNumber(int n) {
        // 功能：找到大于n的最小"美好数"
        // 美好数定义：对于数中的每个数字d，其在数中出现的次数恰好为d（如22中2出现2次，122中1出现1次、2出现2次）
        
        // 高性能实现思路：
        // 预计算所有可能的"美好数"：经分析，符合条件的数数量极少（仅115个），可提前枚举并按升序存储
        // 二分查找：利用有序数组的特性，通过upper_bound快速定位第一个大于n的美好数，时间复杂度O(log k)，k为美好数总数（115）
        
        // 预存储所有"美好数"（按升序排列）
        vector<int> vec{
            0,       1,       22,     122,    212,    221,    333,     1333,
            3133,    3313,    3331,   4444,   14444,  22333,  23233,   23323,
            23332,   32233,   32323,  32332,  33223,  33232,  33322,   41444,
            44144,   44414,   44441,  55555,  122333, 123233, 123323,  123332,
            132233,  132323,  132332, 133223, 133232, 133322, 155555,  212333,
            213233,  213323,  213332, 221333, 223133, 223313, 223331,  224444,
            231233,  231323,  231332, 232133, 232313, 232331, 233123,  233132,
            233213,  233231,  233312, 233321, 242444, 244244, 244424,  244442,
            312233,  312323,  312332, 313223, 313232, 313322, 321233,  321323,
            321332,  322133,  322313, 322331, 323123, 323132, 323213,  323231,
            323312,  323321,  331223, 331232, 331322, 332123, 332132,  332213,
            332231,  332312,  332321, 333122, 333212, 333221, 422444,  424244,
            424424,  424442,  442244, 442424, 442442, 444224, 444242,  444422,
            515555,  551555,  555155, 555515, 555551, 666666, 1224444, 1242444,
            1244244, 1244424, 1244442};

        // 利用upper_bound在有序数组中找到第一个大于n的元素，即为结果
        // upper_bound基于二分查找实现，时间复杂度O(log 115)≈O(1)，性能极高
        return *std::ranges::upper_bound(vec.begin(), vec.end(), n);
    }
};